package main

import "fmt"

func heapify(nums []int,i int,n int){
	max:=i
	c1:=2*i+1
	c2:=2*i+2
	if c1<n && nums[max]<nums[c1]{
		max = c1
	}
	
	if c2<n && nums[max] < nums[c2]{
		max = c2
	}
	
	if max!=i{
		nums[i],nums[max] = nums[max],nums[i]
		heapify(nums,max,n)
	}
}

func buildHeap(nums []int){
	n:=len(nums)
	for i:=n/2-1;i>=0;i--{
		heapify(nums,i,n)
	}
}

func heapsort(nums []int){
	n:=len(nums)
	buildHeap(nums)
	for i:=n-1;i>=0;i--{
		swap(nums,0,i)
		heapify(nums,0,i)
	}
}

func swap(nums []int,a,b int){
	nums[a],nums[b] = nums[b],nums[a]
}

func main() {
	nums := []int{3, 6, 2, 1, 6, 9}
	heapsort(nums)
	fmt.Println(nums)
}
